package org.usmile.algorithms.learn.graph.dfs;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

import java.util.Arrays;

public class BiPartitionDetection {
    public boolean isBiPartition(Graph graph) {
        int[] colors = new int[graph.getV()];
        Arrays.fill(colors, -1);

        for (int v = 0; v < graph.getV(); v++) {
            if (colors[v] == -1) {
                if (!dfs(graph, v, 0, colors)) {
                    return false;
                }
            }
        }

        return true;
    }

    private boolean dfs(Graph graph, int v, int color, int[] colors) {
        colors[v] = color;
        for (int w : graph.adj(v)) {
            if (colors[w] == -1) {
                if (!dfs(graph, w, 1 - color, colors)) {
                    return false;
                }
            } else {
                if (colors[w] == colors[v]) {
                    return false;
                }
            }
        }

        return true;
    }


    public static void main(String[] args) {
        Graph graph = new AdjList(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        System.out.println(new BiPartitionDetection().isBiPartition(graph));
    }
}
